class TerrNode {
    public int val;
    public TerrNode left;
    public TerrNode right;

    public TerrNode(int val) {
        this.val = val;
    }
}
public class TreeSo {//二叉搜索树
    public TerrNode root;
    public boolean charu(int val) {
        if(this.root==null) {
            TerrNode uer =new TerrNode(val);
            this.root=uer;
            return true;
        }
        TerrNode uer = new TerrNode(val);
        TerrNode str =null;
        TerrNode ret =root;
        while(ret!=null) {
            if(ret.val==val) {
                return false;
            }else if(ret.val>val) {
                str=ret;
                ret=ret.left;
            }else if(ret.val<val) {
                str=ret;
                ret=ret.right;
            }
        }
        if(val>str.val) {
            str.right=uer;
        }
        if(val<str.val) {
            str.left=uer;
        }
        return true;
    }
    public boolean chazhao(int val) {
        TerrNode uer =root;
        while(uer!=null) {
            if(val<uer.val) {
                uer=uer.left;
            }else if(val>uer.val){
                uer=uer.right;
            }else {
                return true;
            }
        }
        return false;
    }
    public void zhoxu(TerrNode root) {//中序遍历
        if(root==null) {
            return;
        }
        zhoxu(root.left);
        System.out.print(root.val+" ");
        zhoxu(root.right);
    }
}
